// hdu5919
// 题意：
// 给定一个长度为n(<=2*10^5)的序列a(ai<=2*10^5)，现在有m(<=2*10^5)个询问，
// 每个询问询问一个区间[l, r]，假如说这个区间内有k个不相同的数，你要输出
// 按下标排序第ceil(k/2)个数第一次出现位置的下标。
//
// 题解：
// 可持久化线段树。一个区间不相同数个数这个是经典应用。
// 这题要求第k/2个数第一次出现的位置，我们可以从后往前建可持久化线段树，
// 每次遇到一个元素如果之前出现过，就把之前的删掉。这样可以保证从左往右，
// 现在这个在对应位置的线段树里的数是第一个出现的。
//
// 然后要找第 k/2 个有两种方法，第一种直接二分，时间比较紧。另一种可以
// 像找第 k 大一样，一次二分就可以找到对应数（利用线段树本身很好的二分
// 性质）。
//
// ml:run = $bin < input
// ml:opt = 0
// ml:ccf += -g
#include <cstdio>
#include <algorithm>
#include <unordered_map>

int const maxn = 200007;
int const maxm = maxn * 60;
int T[maxm], lson[maxm], rson[maxm], c[maxm], alloc;
int a[maxn];
int n, m;

std::unordered_map<int, int> id;

int build(int l, int r)
{
    int root = alloc++;
    c[root] = 0;
    if (l != r) {
        int mid = (l + r) / 2;
        lson[root] = build(l, mid);
        rson[root] = build(mid + 1, r);
    }
    return root;
}

int update(int root, int pos, int v)
{
    int newroot = alloc++;
    int tmp = newroot;
    c[newroot] = c[root] + v;
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) / 2;
        if (pos <= mid) {
            lson[newroot] = alloc++;
            rson[newroot] = rson[root];
            newroot = lson[newroot];
            root = lson[root];
            r = mid;
        } else {
            rson[newroot] = alloc++;
            lson[newroot] = lson[root];
            newroot = rson[newroot];
            root = rson[root];
            l = mid + 1;
        }
        c[newroot] = c[root] + v;
    }
    return tmp;
}

int query(int root, int tr)
{
    int ret = 0;
    int l = 1, r = n;
    while (tr < r) {
        int mid = (l + r) / 2;
        if (tr <= mid) {
            r = mid;
            root = lson[root];
        } else {
            ret += c[lson[root]];
            root = rson[root];
            l = mid + 1;
        }
    }
    return ret + c[root];
}

void init() { id.clear(); alloc = 0; }

int calc(int tl, int tr)
{
    int k = (query(T[tl], tr) + 1) / 2;
    int l = 1, r = n, root = T[tl];
    while (l != r) {
        int mid = (l + r) / 2;
        int tmp = c[lson[root]];
        if (tmp >= k) {
            r = mid;
            root = lson[root];
        } else {
            l = mid + 1;
            root = rson[root];
            k -= tmp;
        }
    }
    return l;
}

int main()
{
    int tcase; std::scanf("%d", &tcase);
    for (int ti = 1; ti <= tcase; ti++) {
        std::printf("Case #%d:", ti);
        init();
        std::scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) std::scanf("%d", &a[i]);
        T[n + 1] = build(1, n);
        for (int i = n; i > 0; i--) {
            int tmp = T[i + 1];
            if (id.count(a[i])) tmp = update(T[i + 1], id[a[i]], -1);
            T[i] = update(tmp, i, 1);
            id[a[i]] = i;
        }
        int ans = 0;
        for (int i = 0, l, r, ll, rr; i < m; i++) {
            std::scanf("%d%d", &ll, &rr);
            l = std::min((ll + ans) % n + 1, (rr + ans) % n + 1);
            r = std::max((ll + ans) % n + 1, (rr + ans) % n + 1);

            /* std::printf("--> %d %d\n", l, r); */

            std::printf(" %d", (ans = calc(l, r)));
        }
        std::printf("\n");
    }
}

